{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "好哒，这一节聊一下什么是马尔科夫随机场/概率无向图模型，顾名思义，就是用无向图表达的随机变量的联合概率分布，比如如下的一个图，就是包含了4个随机变量的概率无向图，它描述了随机变量与随机变量之间的关系：   \n",
    "![avatar](./source/12_无向图demo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.概率计算\n",
    "一看这图首先会想到如何计算它的联合概率分布？先说求解方式：它的联合概率分布表示为其**最大团**上的**随机变量的函数**的乘积。这里有两点不好理解，什么是最大团？随机变量的函数又是什么？ 下面对其做介绍，   \n",
    "\n",
    "#### 团与最大团\n",
    "无向图中任何两个节点均有边连接的节点子集构成一个团，若这个团不能再加入任何一个其他的图中节点，则称为最大团。    \n",
    "\n",
    "所以上面的无向图中：    \n",
    "\n",
    "（1）团有7个：{X1,X2},{X1,X3},{X2,X3},{X2,X4},{X3,X4},{X1,X2,X3},{X2,X3,X4}   \n",
    "\n",
    "（2）最大团有两个：{X1,X2,X3},{X2,X3,X4}    \n",
    "\n",
    "注意：{X1,X2,X3,X4}不构成最大团，因为X1与X4之间没有连接   \n",
    "\n",
    "#### 随机变量的函数：势函数  \n",
    "\n",
    "关于随机变量的函数，称为势函数，通常写作：   \n",
    "\n",
    "$$\n",
    "\\psi_C(X_C)\n",
    "$$   \n",
    "这里，$X_C$即表示一个最大团，而且要求$\\psi_C(X_C)>0$，通常会定义为一个指数函数  \n",
    "\n",
    "#### 联合概率计算：Hammersley-Clifford定理\n",
    "\n",
    "所以，其联合概率分布$P(X)$的可以表示为如下形式：   \n",
    "\n",
    "$$\n",
    "P(X)=\\frac{1}{Z}\\prod_C\\psi_C(X_C)\\\\\n",
    "Z=\\sum_X\\prod_C\\psi_C(X_C)\n",
    "$$   \n",
    "\n",
    "这里，$C$是无向图的最大团，$X_C$是其对应的随机变量，$\\psi_C(X_C)$是$C$上定义的严格正函数，乘积是在无向图所有的最大团上进行的，这便是Hammersley-Clifford定理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二.马尔科夫随机场的定义\n",
    "这里再倒回来说一下马尔科夫随机场的定义，其实我们在实际问题中很难遇到需要考究其定义的情况，因为既然无向图都画出来了，说明肯定是满足其定义的~~~ ，好的，要构建一个马尔科夫随机场需要满足如下三个定义   \n",
    "\n",
    "#### 成对马尔科夫性\n",
    "设$u$和$v$是无向图$G$中任意两个没有边直接连接的节点，其对应的随机变量分别为$X_u$,$X_v$，剩余的所有节点为$O$，对应的随机变量组为$X_O$，那么在给定$X_O$的条件下，随机变量$X_u$与$X_v$是条件独立的，即   \n",
    "\n",
    "$$\n",
    "P(X_u,X_v\\mid X_O)=P(X_u\\mid X_O)P(X_v\\mid X_O)\n",
    "$$   \n",
    "\n",
    "PS：可以想象所有$O$构成了一堵墙将$u$与$v$隔断\n",
    "\n",
    "#### 局部马尔科夫性\n",
    "设$u\\in V$是无向图$G$中任意一个节点，$W$是与$v$有边直接相连的所有节点，$O$是$v$和$W$以外的其他所有节点，$v$对应的随机变量是$X_v$，$W$对应的随机变量组是$X_W$，$O$对应的随机变量组是$X_O$，那么在给定$X_W$的条件下，$X_u$与$X_O$是条件独立的，即   \n",
    "\n",
    "$$\n",
    "P(X_u,X_O\\mid X_W)=P(X_u\\mid X_w)P(X_O\\mid X_W)\n",
    "$$    \n",
    "\n",
    "PS：可以想象所有$W$构成了一堵$v$的围墙，将它与外界隔离   \n",
    "\n",
    "#### 全局马尔科夫性\n",
    "设节点集合$A,B$是无向图$G$中被节点集合$C$分开的任意节点集合，它们对应的随机变量组分别为$X_A,X_B,X_C$，那么在$X_C$给定的条件下，$X_A$与$X_B$条件独立：   \n",
    "\n",
    "$$\n",
    "P(X_A,X_B\\mid X_C)=P(X_A\\mid X_C)P(X_B\\mid X_C)\n",
    "$$  \n",
    "\n",
    "其实，这三个定义是互相等价的，所以只需其一即可"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
